package com.example.demo.LinearTable.LRU;

import java.util.HashMap;

/**
 * LRU (最近最少使用) 缓存机制要求支持以下操作： 获取数据 get 和 写入数据 put
 * 查询数据：获取数据 get(key)，如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1
 * 写入数据：写入数据 put(key, value) ，如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 * 在 O(1) 时间复杂度内完成这两种操作？ （双向链表+hash散列表）
 * 双向链表：保证写入O（1），hash散列表：保证读取O（1）
 * <p>
 * 数据结构：null 头节点（pre data next） 。。。 尾结点（pre data next） null
 */
public class LRU {

    private int capacity;
    private HashMap<Integer, Node> cache;
    private Node head;
    private Node tail;


    public LRU(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        recentUseByCached(node);
        return node.getValue();
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        // 情况1：缓存已存在
        Node node = cache.get(key);
        if (node != null) {
            node.setValue(value);
            recentUseByCached(node);
            return;
        }

        // 情况2：缓存中不存在该key
        node = new Node(key, value);
        recentUseByUnCached(node);
    }

    /**
     * 情况1：缓存已存在: （1）删除原节点；（2）将节点头插至头结点；
     */
    private void recentUseByCached(Node node) {
        Node pre = node.getPre();
        Node next = node.getNext();
        // 子情况1.1：头结点
        if (pre == null) {
            return;
        }

        // 子情况1.2：尾结点，删除尾结点
        if (next == null) {
            pre.setNext(null);
            tail = pre;
        } else {
            // 子情况1.3：普通节点，删除普通节点
            next.setPre(pre);
            pre.setNext(next);
        }

        // 头插入，并移动头指针
        node.setNext(head);
        node.setPre(null);
        head.setPre(node);
        head = node;
    }

    /**
     * 情况2：缓存中不存在该key，（1）如果缓存已满，删除尾节点；（2）将节点头插至头结点；
     */
    private void recentUseByUnCached(Node node) {
        // 子情况2.1：缓存已满，需要先删除尾结点数据
        if (cache.size() == capacity) {
            // 注意要删缓存+链表的数据
            cache.remove(tail.getKey());
            tail = tail.getPre();
            if (tail != null) {
                tail.setNext(null);
            }
        }
        // 子情况2.2: 缓存未满，直接头插入即可
        // 放入缓存
        cache.put(node.getKey(), node);
        // 放入链表（头插）
        node.setNext(head);
        node.setPre(null);
        // 注意：初始状态，即tail==head==null
        if (head != null) {
            head.setPre(node);
        }
        head = node;
        if (tail == null) {
            tail = node;
        }
    }

}

/**
 * 双向链表
 */
class Node {
    private int key;
    private int value;
    private Node pre, next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public Node getPre() {
        return pre;
    }

    public void setPre(Node pre) {
        this.pre = pre;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getKey() {
        return key;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

class GateTest {
    public static void main(String[] args) {
        LRU cache = new LRU( 2 /* 缓存容量 */ );

        cache.put(1, 1);
        cache.put(2, 2);
        int i = cache.get(1);// 返回  1
        System.out.println(i);
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        int i1 = cache.get(2);// 返回 -1 (未找到)
        System.out.println(i1);

        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        int i2 = cache.get(1);   // 返回 -1 (未找到)
        int i3 = cache.get(3);       // 返回  3
        int i4 = cache.get(4);       // 返回  4
        System.out.println(i2);
        System.out.println(i3);
        System.out.println(i4);
    }
}


